package demo.letcode.top100;

/**
 * s1='people' s2=‘eplm’
 * 求最长的公共子串
 *
 * @author taqo
 * @date 2021/5/8
 */
public class _最长公共子串 {

    public static void main(String[] args) {
        String s1 = "people";
        String s2 = "eple";
        m0(s1, s2);
//        a(s1, s2);
//        a2(s1, s2);
    }

    private static void m0(String s1, String s2) {
        // 动态规划
        //字符串1: abcde
        //字符串2: acbce
        //
        //动态规划表填充过程:
        //   ∅  a  c  b  c  e
        //∅  0  0  0  0  0  0
        //a   0  1  0  0  0  0
        //b   0  0  0  1  0  0
        //c   0  0  1  0  2  0
        //d   0  0  0  0  0  0
        //e   0  0  0  0  0  1
        // dp[i][j]的含义：以s1[i-1]和s2[j-1]结尾的公共子串长度
        //递推关系：
        //  字符相同：dp[i][j] = dp[i-1][j-1] + 1
        //  字符不同：dp[i][j] = 0
        //
        //为什么看对角线：因为公共子串在两个字符串中是连续的
        //
        //如何提取结果：找到dp表中的最大值，然后向前回溯对应长度
        int maxLen = 0; // 最长公共字串的长度
        int endIdx = 0; // 在str1中结束的位置
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m + 1][n + 1];// dp[i][j]表示以s1第i个字符和s2第j个字符结尾的最长公共字串长度
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (dp[i][j] > maxLen) {
                        maxLen = dp[i][j];
                        endIdx = i - 1; // 记录结束位置
                    }
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        System.out.println(s1.substring(endIdx - maxLen + 1, endIdx + 1));
    }

    private static void a2(String s1, String s2) {
        // 暴力枚举
        String s3 = "";
        for (int i = 0; i < s1.length(); i++) { // 遍历第一个字符串的每个位置为起点
            for (int j = 0; j < s2.length(); j++) { // 遍历第二个字符串的每个位置
                int k = 0;
                // 从当前位置开始比较
                while (i + k < s1.length() && j + k < s2.length() && s1.charAt(i + k) == s2.charAt(j + k)) {
                    k++;
                }

                if (k > s3.length()) {
                    s3 = s1.substring(i, i + k);
                }
            }
        }
        System.out.println(s3);
    }

    private static void a(String s1, String s2) {
        // String s1 = "people";
        // String s2 = "eplm";
        int max = 0;
        int dp[][] = new int[s1.length() + 1][s2.length() + 1];
        for (int i = 0; i < s1.length(); i++) {
            for (int j = 0; j < s2.length(); j++) {
                char c = s1.charAt(i);
                char c1 = s2.charAt(j);
                // 为什么比较i-1而设置i,j
                if (s1.charAt(i) == s2.charAt(j)) {
                    if (i > 0 && j > 0) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                        max = Math.max(max, dp[i][j]);
                    } else {
                        dp[i][j] = 1;
                    }
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        System.out.println(max);
        b();
    }

    public static void b() {
        String s1 = "people";
        String s2 = "eple";

        int max = 0;

        int dp[][] = new int[s1.length() + 1][s2.length() + 1];
        for (int i = 0; i < s1.length(); i++) {
            for (int j = 0; j < s2.length(); j++) {
                if (s1.charAt(i) == s2.charAt(j)) {
                    if (i > 0 & j > 0) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                        max = Math.max(max, dp[i][j]);
                    } else {
                        dp[i][j] = 1;
                    }
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        System.out.println(max);
    }
}
